package Euler78;

import java.util.*;

public class CoinPartitions 
{
	public static void main(String[] args) 
	{
		int num = 3;
		System.out.println(waysToPartition(Arrays.asList(num), num));
	}
	
	static int waysToPartition(List<Integer> array, int num)
	{
		
		System.out.println(array);
		
		//Base case, an array of size num.
		if(array.size() == num)
		{
			return 1;
		}
		//Take one step and recursively call this function.
		else
		{
			List<Integer> arr = new ArrayList<Integer>();
			
			//Traverse the array from right to left until one of the values is greater than 1.
			for(int i = array.size()-1; i>=0; i--)
			{
				int n = array.get(i);
				if(n>1)
				{
					for(int j = 0; j < array.size(); j++)
					{
						if(j==i)
						{
							if(j==0)
							{
								arr.add(n-1);
								arr.add(num-((n-1)));
								
								return waysToPartition(arr, num) + 1;
							}
							else
							{
								arr.add(n-1);
								arr.add(1);
							}
						}
						else
						{
							arr.add(array.get(j));
						}
					}
					
					return waysToPartition(arr, num) + 1;
				}
				else if(i==0)
				{
					return 0;
				}	
			}
			
			return 0;
		}
	}
}
